package com.interview.ujiuye4;

import java.util.Stack;

public class DataChain {
    
    private  DataNode head;
    
    public DataChain(int size) {
        DataNode head = new DataNode(0);
        DataNode cur = head;
        for (int i = 1; i < size; i++) {
            DataNode tmp = new DataNode(i);
            cur.setNext(tmp);
            cur = tmp;
        }
        this.head = head;
    }

    public DataNode getHead() {
        return head;
    }

    public void setHead(DataNode head) {
        this.head = head;
    }
    public static void main(String... strings) {
        DataChain chain = new DataChain(10);
        printChain(chain.getHead());
        System.out.println("单链表反转....");
        printChain(reverse2(chain.getHead()));
    }

    public static void printChain(DataNode head) {
        StringBuilder sb = new StringBuilder();
        DataNode cur = head;
        sb.append(cur.getData());
        while (null != cur.getNext()) {
            sb.append(" -> ");
            sb.append(cur.getNext().getData());
            cur = cur.getNext();
        }
        System.out.println(sb.toString());
    }

    /**
     * 递归实现 当栈深度大于12000 则会出现StakOverflowError
     *
     * @param head
     * @return
     */
    public static DataNode reverse1(DataNode head) {
        if (null == head || null == head.getNext())
            return head;
        DataNode revHead = reverse1(head.getNext());
        head.getNext().setNext(head);
        head.setNext(null);
        return revHead;
    }
    /**
     * 遍历实现 通用实现方法
     *
     * @param head
     * @return
     */
    public static DataNode reverse2(DataNode head) {
        //如果链表没有元素或者只有一个元素，不反转直接返回链表本身
        if (null == head || null == head.getNext())
            return head;
        //当链表超过两个及以上就需要反转
        DataNode pre = head;//用于保存当前节点的前一个节点
        DataNode cur = head.getNext();//cur保存当前节点
        while (null != cur.getNext()) {
            DataNode tmp = cur.getNext();//获取当前节点的下一个元素
            cur.setNext(pre);//把当前节点的next指向前一个元素
            pre = cur;//把当前节点改为前一个节点（其实就是前一个元素后移一位）。
            cur = tmp;//把当前节点的下一个节点改为当前节点（其实就是前一个元素后移一位）。
        }
        cur.setNext(pre);
        head.setNext(null);
        return cur;
    }
    /**
     * 方法3 利用其他数据结构 stack
     * @param head
     * @return
     */
    public static DataNode reverse3(DataNode head) {
        Stack<DataNode> stack = new Stack<DataNode>();
        for (DataNode node = head; null != node; node = node.getNext()) {
            stack.add(node);
        }
        DataNode reHead = stack.pop();
        DataNode cur = reHead;
        while(!stack.isEmpty()){
            cur.setNext(stack.pop());
            cur = cur.getNext();
            cur.setNext(null);
        }
        return reHead;
    }

}